package com.wfs.suanfa.leet;

/**
 * 什么是“Trie树”？
 * Trie树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
 * 构建好Trie树后，在其中查找字符串的时间复杂度是O(k)，k表示要查找的字符串的长度。
 * @author wfs
 * @date 2022-11-16 17:40
 */
public class Trie {
    // 存储无意义字符
    private TrieNode root = new TrieNode('/');

    public static void main(String[] args) {
        Trie trie=new Trie();
        trie.insert("abcdefghigk".toCharArray());
        System.out.println(trie.find("abc".toCharArray()));
        System.out.println(trie.find("abcdefghigk".toCharArray()));
    }

    // 往Trie树中插入一个字符串
    public void insert(char[] text) {
        TrieNode p = root;
        for (int i = 0; i < text.length; i++) {
            int index=text[i]-'a';
            if (p.children[index] == null){
                TrieNode newNode=new TrieNode(text[i]);
                p.children[index]=newNode;
            }
            p=p.children[index];
        }
        p.isEndingChar = true;
    }
    // 在Trie树中查找一个字符串
    public boolean find(char[] pattern) {
        TrieNode p = root;
        for (int i = 0; i < pattern.length; ++i) {
            int index = pattern[i] - 'a';
            if (p.children[index] == null) {
                return false; // 不存在pattern
            }
            p = p.children[index];
        }
        // 不能完全匹配，只是前缀
        if (p.isEndingChar == false){
            System.out.println("部分匹配");
            return false;
        } else {
            // 找到pattern
         return true;
        }
    }

    public class TrieNode {
        public char data;
        public TrieNode[] children = new TrieNode[26];
        public boolean isEndingChar = false;
        public TrieNode(char data) {
            this.data = data;
        }
    }
}
